/**
 * https://leetcode.cn/submissions/detail/582268996/
 * 200. 岛屿数量
 * Medium, 黄伟杰 2024.11.22
 * 并查集
 */

class union_find
{
public:
    // 构造从 0 到 n - 1 的节点
    union_find(vector<vector<char>> &grid)
    {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    parent.push_back(i * n + j);
                    count++;
                }
                else
                    parent.push_back(-1);
                rank.push_back(0);
            }
        }
    }
    void pair(int index1, int index2)
    {
        parent[find(index2)] = find(index1);
    }
    // 找到根节点
    int find(int index)
    { // 递归函数，找根节点的同时进行路径压缩
        if (parent[index] != index)
        {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
    void unite(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty)
        {
            if (rank[rootx] < rank[rooty])
            {
                swap(rootx, rooty);
            }
            pair(rootx, rooty);
            if (rank[rootx] == rank[rooty])
                rank[rootx] += 1;
            --count;
        }
    }
    int getcount()
    {
        return count;
    }

private:
    vector<int> parent;
    vector<int> rank;
    int count;
};
class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int nr = grid.size();
        if (!nr)
            return 0;
        int nc = grid[0].size();
        union_find uf(grid);
        int num_islands = 0;
        for (int r = 0; r < nr; ++r)
        {
            for (int c = 0; c < nc; ++c)
            {
                if (grid[r][c] == '1')
                {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r - 1][c] == '1')
                        uf.unite(r * nc + c, (r - 1) * nc + c);
                    if (r + 1 < nr && grid[r + 1][c] == '1')
                        uf.unite(r * nc + c, (r + 1) * nc + c);
                    if (c - 1 >= 0 && grid[r][c - 1] == '1')
                        uf.unite(r * nc + c, r * nc + c - 1);
                    if (c + 1 < nc && grid[r][c + 1] == '1')
                        uf.unite(r * nc + c, r * nc + c + 1);
                }
            }
        }

        return uf.getcount();
    }
};